1. Field of the Invention
This invention relates to a fast adder chain. More particularly, the invention relates to an adder chain which is operative to add together at least one pair of digital words and includes a plurality of adder blocks in cascade arrangement.
2. Discussion of the Related Art
As is well known, adder chains are used in a variety of circuit arrangements designed to meet a range of different applicational demands. A typical example of their utility is related to FIR Finite Impulse Response filters, wherein the adders are adapted to implement part of the transfer function which is characteristic of the filter.
A number of prior art adder chains are known in the art. Such prior art adder chains have a common drawback in that they are all quite slow in yielding the result of the sum operation. Some of these prior approaches have been described in detail in Joseph Cavanagh's "Digital Computer Arithmetics", published by McGraw-Hill.
For completeness of discussion, briefly reviewed herein below are the most commonly adopted solutions to the problem of providing N-bit parallel adders for two's complement, fixed point numbers. A first adder is known as the "Look-Ahead Carry" type and is effective to simultaneously input carries to each block at the location of each bit. The carries are generated from three count levels, whereas the sum is obtained from two levels.
It follows that the maximum propagation delay will be equal to five clock impulses. However, the final carry requires a logic AND gate with N+1 inputs, which can only be implemented by a network of cascade-connnected gates. It can be appreciated that this involves additional delay in the signal propagation.
Another adder, known as the "Select Carry" type, has a structure in which the operands are divided into groups, and each group is implemented using the same logic as in the first adder above. This second adder is not particularly fast, and requires highly complex circuitry.
A third prior approach, referred to as the "By-Pass Carry", attempts to reduce the time required to generate the sum by speeding up the carry determining operation for the carry to be input to a given cell. For this purpose, an overriding step is provided for the carry to override one chain stage when either operand already has a logic value of one at the given location. The attainable rate with such an approach is not a significantly fast one.
A further type of adder is that known in the art as "Carry Save Adder" or "pseudoadder", and includes a combination network which, when input three numbers of N bits each, will output two more N-bit numbers referred to as the "pseudosum" and "pseudocarry". This prior art adder requires a final stage to add the pseudosum and pseudocarry together, with the pseudocarry suitably shifted one position.
In summary, all of the prior art adders have the disadvantage of being quite slow in performing the sum operation despite the different forms in which they have been embodied. Further, such adders include considerable circuit complexity, which greatly increases the integrated circuit area that must be devoted to the sum operation.
The underlying technical problem solved by this invention is to provide an adder chain which has such structural and functional characteristics as to allow the sum operation to be performed at a very fast rate, and with reduced silicon area requirements, thereby overcoming the limitations of the prior art.